
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //法二：自上而下dp
    public int coinChange(int[] coins, int amount) {
        //初始条件检查
        if (amount < 1)
            return 0;
        //DP入口：注意函数名不一样
        return coinchange1(coins, amount, new int[amount + 1]);
    }

    /**
     * 自顶向下的DP方法
     * coins：硬币面额
     * res：余额
     * count数组：count[i] 余额为i的找零钱的最少个数
     */
    private int coinchange1(int[] coins, int res, int[] count) {
        //结束条件1：此路径不通
        if (res < 0) return -1;
        //结束条件2：余额为0，成功结束
        if (res == 0) return 0;
        //之前已经计算过这种情况，直接返回结果
        if (count[res] != 0) return count[res];
        int min = Integer.MAX_VALUE;
        //遍历当前递归子树的每一种情况
        for (int coin : coins) {
            //用一下当前coin面值的硬币的结果，restmp用当前coin得到的找钱的最少个数
            int restmp = coinchange1(coins, res - coin, count);
            //当前情况用的硬币个数更少，更新min
            if (restmp >= 0 && restmp < min) {
                min = restmp + 1;
            }
        }
        //这么写，防止了无解的情况
        count[res] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[res];
    }


}

//leetcode submit region end(Prohibit modification and deletion)
